package sort

import "math/rand"

/*
	平均时间复杂度：O(nlogn)
	最好情况：O(nlogn)
	最坏情况：O(n²)
	空间复杂度：O(nlogn) 需要一个栈的空间来递归
	排序方式：Inplace
	稳定性：不稳定 在左右指针相遇的时候，基准移到指针所指向的位置，那么原先与基准相同的数，可能从在基准后面，移动到基准前面
*/
func QuickSort(nums []int) {
	quick(nums, 0, len(nums)-1)
}

func quick(nums []int, left int, right int) {

	if left >= right {
		return
	}

	base := nums[left]

	i, j := left, right

	// 把比基准小的移动到基准的左边，比基准大的移动到右边
	// 基准是最左边的数，那么先移动右指针，否则先移动左指针
	// 因为如果先移动左指针，最后一次移动（即移动至左右指针碰到），仅能移动一次指针（即仅移动先指向的指针）
	// 移动前，右指针所指向的数一定比基准大
	// 那么，左指针先移动，左右指针相遇，此时同时指向比基准大的数，与基准交换后，基准的左边就出现了比自己小的数
	for i < j {
		for nums[j] >= base && i < j {
			j--
		}

		for nums[i] <= base && i < j {
			i++
		}

		if i < j {
			nums[i], nums[j] = nums[j], nums[i]
		}
	}

	nums[i], nums[left] = nums[left], nums[i]

	quick(nums, left, i-1)
	quick(nums, i+1, right)
}

func QuickSort2(nums []int) {
	if len(nums) <= 1 {
		return
	}

	head, tail, i := 0, len(nums)-1, 0

	privot := rand.Intn(len(nums))

	nums[privot], nums[tail] = nums[tail], nums[privot]

	// head-i 都是比nums[tail]大的
	// 如果nums[i]比nums[tail]小，那么就要把他移动到head的位置
	// 然后head的索引+1，这样[0,head)就是小于tail,(head:]都是大于tail
	for i < tail {
		if nums[i] < nums[tail] {
			nums[i], nums[head] = nums[head], nums[i]
			head++
			i++
		} else {
			i++
		}
	}

	if nums[head] > nums[tail] {
		nums[head], nums[tail] = nums[tail], nums[head]
	}

	QuickSort2(nums[:head])
	QuickSort2(nums[head:])
}
